package com.burns.study.leetcode.learning.chapter1;/**
 * Created by burns.
 *
 * @author <a href="http://www.esoon-soft.com/">burns</a>
 * @date 2021/07/03 8:11
 */

import java.util.HashMap;
import java.util.Map;

/**
 哈希表
 思路及算法

 注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

 使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。

 这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配

 复杂度分析

 时间复杂度：O(N)O(N)，其中 NN 是数组中的元素数量。对于每一个元素 x，我们可以 O(1)O(1) 地寻找 target - x。

 空间复杂度：O(N)O(N)，其中 NN 是数组中的元素数量。主要为哈希表的开销。
 * @ClassName TwoSum
 * @Author Burns
 * @DAte 2021/7/3 8:11
 */
public class TwoSum_2 {
    public static void main(String[] args){
        int[] nums = {2,7,11,15};
        int target = 17;
        int[] ints = twoSum(nums, target);

        StringBuilder sb = new StringBuilder("检索结果下标：");
        for (int i=0;i<ints.length;i++){
            sb.append(ints[i]+"、");
        }
        System.out.println(sb);

    }
    public static int[] twoSum(int[] nums, int target) {
        //定义一个hashmap,其中key存放nums的每个数值，value存放nums的每个值的下标
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        //从头到尾遍历nums
        for (int i = 0; i < nums.length; ++i) {
            //判断map中是否存在一个数使target-当前数，如果存在则返回，如果不存在，则插入到map中。
            if (hashMap.containsKey(target - nums[i])) {
                return new int[]{hashMap.get(target - nums[i]), i};
            }
            hashMap.put(nums[i], i);
        }
        return new int[0];
    }

}
